package codingforgreat.class36;


import java.util.Arrays;

// 来自腾讯
// 给定一个正数数组arr，代表每个人的体重。给定一个正数limit代表船的载重，所有船都是同样的载重量
// 每个人的体重都一定不大于船的载重
// 要求：
// 1, 可以1个人单独一搜船
// 2, 一艘船如果坐2人，两个人的体重相加需要是偶数，且总体重不能超过船的载重
// 3, 一艘船最多坐2人
// 返回如果想所有人同时坐船，船的最小数量
public class Class08_MinBoatEvenNumbers {
    public static int minBoat(int[] arr, int limit) {
        Arrays.sort(arr);
        int ji = 0;
        int ou = 0;
        for(int i = 0;i <  arr.length;i++){
            if((arr[i] & 1) == 0){
                ou++;
            }else{
                ji++;
            }
        }
        int[] jis = new int[ji];
        int[] ous = new int[ou];
        for(int i = arr.length - 1; i >= 0;i--){
            if((arr[i] & 1) == 0){
                ous[--ou] = arr[i];
            }else{
                jis[--ji] = arr[i];
            }
        }
        return min(jis,limit) + min(ous,limit);
    }
    public static int min(int[] arr,int limit){
        int l = 0;
        int r = arr.length -1;
        int res = 0;
        while(l <= r){
            int sum = l == r ? arr[l] : arr[l] + arr[r];
            if(sum < limit){
                r--;
            }else {
                l++;
                r--;
            }
            res++;
        }
        return res;
    }

}
